


class Solution:
    def combinationSum(self, candidates, target):
        ans = []
        path = []
        n = len(candidates)

        def dfs(i, t):
            if t == 0:
                ans.append(path.copy())
                return
            if t < 0 or i == n :
                return
            
            # i不选
            dfs(i + 1, t)

            # if t >= candidates[i]:
            path.append(candidates[i])
            dfs(i, t - candidates[i])

            path.pop()

        
        dfs(0, target)

        return ans

